题目大意
现在有如下的字母与数字的对应关系：1-A, 2-B, …26-Z。给定一个由数字组成的字符串，判断按照上面的映射可以转换成多少种不同的字符串。
解题思路
动态规划
参考：http://www.cnblogs.com/zuoyuan/p/3783897.html
和爬梯子相当像，但需要分情况考虑而不能一味dp[i]=dp[i-1]+dp[i-2]
解码有多少种方法。一般求“多少”我们考虑使用dp。状态方程如下：
当s[i-2:i]这两个字符是10~26但不包括10和20这两个数时，比如21，那么可以有两种编码方式（BA，U），所以dp[i]=dp[i-1]+dp[i-2]
当s[i-2:i]等于10或者20时，由于10和20只有一种编码方式，所以dp[i]=dp[i-2]
当s[i-2:i]不在以上两个范围时，如09这种，编码方式为0。
而31这种，dp[i]=dp[i-1]。
注意初始化时：dp[0]=1,dp[1]=1
举个例子：
1
2
3
4
5
6
| [1, 1]
[1, 1, 2] 12
[1, 1, 2, 3] 23
[1, 1, 2, 3, 3] 34
[1, 1, 2, 3, 3, 3] 42
[1, 1, 2, 3, 3, 3, 6] 21
|
首先12，有两种可能，所以dp[3]=1+1
然后23，两种可能，所以1+2 = 3
然后34，从全局看，123多了4之后由于不能和前面的组成新组合，只能自己独立，所以可能输并不会变化
42和34一样理解，不增加新可能。
到了21，由于其有两种可能，那么使得之前的都会累积成为新变种，所以是**dp[i]=dp[i-1]+dp[i-2]**，这一步是最重要的
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if s == "" or s[0] == "0":
return 0
if len(s) == 1:
return 1
dp = [1,1]
for i in range(2, len(s)+1):
# print dp, s[i-2:i]
if 10 <= int(s[i-2:i]) <= 26 and s[i-1] != '0': # 当s[i-2:i]这两个字符是10~26但不包括10和20这两个数时，比如21，那么可以有两种编码方式（BA，U），所以dp[i]=dp[i-1]+dp[i-2]
dp.append(dp[i-1]+dp[i-2])
elif int(s[i-2:i]) == 10 or int(s[i-2:i]) == 20:
dp.append(dp[i-2]) # 当s[i-2:i]等于10或者20时，由于10和20只有一种编码方式，所以dp[i]=dp[i-2]
elif s[i-1]!='0': #
dp.append(dp[i-1]) # 当s[i-2:i]不在以上两个范围时，如09这种，编码方式为0，而31这种，dp[i]=dp[i-1]
else:
return 0
return dp[-1]
|
总结